Concentration inequalities are indispensable tools for studying thegeneralization capacity of learning models. Hoeffding's and McDiarmid'sinequalities are commonly used, giving bounds independent of the datadistribution. Although this makes them widely applicable, a drawback is thatthe bounds can be too loose in some specific cases. Although efforts have beendevoted to improving the bounds, we find that the bounds can be furthertightened in some distribution-dependent scenarios and conditions for theinequalities can be relaxed. In particular, we propose four types of conditionsfor probabilistic boundedness and bounded differences, and derive severaldistribution-dependent extensions of Hoeffding's and McDiarmid's inequalities.These extensions provide bounds for functions not satisfying the conditions ofthe existing inequalities, and in some special cases, tighter bounds.Furthermore, we obtain generalization bounds for unbounded andhierarchy-bounded loss functions. Finally we discuss the potential applicationsof our extensions to learning theory.
展开▼
